package weekMatch.one_337;

import java.util.Arrays;

public class LeeCode_03_failed {
    public static void main(String[] args) {
//        System.out.println(beautifulSubsets(new int[]{2, 4, 6}, 2));
//        System.out.println(beautifulSubsets(new int[]{1}, 1));
        System.out.println(beautifulSubsets(new int[]{1,2,3,5}, 1));
//        System.out.println(beautifulSubsets(new int[]{4,2,5,9,10,3}, 1));
    }
    private static int beautifulSubsets(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int[][] memo = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dfs(nums, 0, n - 1, memo, k);
    }
    private static int dfs(int[] nums, int i, int j, int[][] memo, int k){
        if (memo[i][j] != -1)
            return memo[i][j];
        if (i > j)
            return 0;
        if (i == j)
            return 1;
        int midS = -1;
        int midE = -1;
        for(int m = j - 1; m >= i; m--){
            if (nums[j] - nums[m] == k){
                midE = m;
                midS = midE;
                while (midS >= i && nums[midS] == midE){
                    midS--;
                }
                break;
            }
        }
        if (midS != -1){
            return memo[i][j] = (dfs(nums, i, midS, memo, k) + dfs(nums, midE + 1, j - 1, memo, k)) * 2;
        }
        return memo[i][j] = dfs(nums, i, j - 1, memo, k) * 2;
    }
}
